<?php
//插入排序（依次与I-1,I-2,I-3...对比寻找插入位置，I对应的值小于I-1的值，I-1的值往后移，依次插入）
//当插入第i(i≥1)个对象时,前面的V[0],V[1],…,V[i−1]已经排好序。这时,用V[i]的排序码与V[i−1],V[i−2],…,V[0]的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。
$arr = [ 1000 , 43 , 54 , 62 , 21 , 66 , 32 , 78 , 36 , 76 , 39 , 10000 , 8222 , 111 , 8797897 , 347824897328 , 27772 , 18723827 , 773 , 288288 ];
$length=count($arr);
for($i=1; $i<$length; $i++) {
	//$i = 0 时，已经排好序===》[1000],此时插入43，[43,1000]，$temp要插入的值

	$temp = $arr[$i];
	echo '<div style="color:red;">'.'----此时将数组下标为'.$i.'的$temp:'.$temp.'插入到排好序的数组中</div>';
	//内层循环控制，寻找插入位置
	for($j=$i-1;$j>=0;$j--) {
		if($temp < $arr[$j]) {
			//发现插入的元素相对更小，交换位置，原来位置上的对象向后顺移。
			$arr[$j+1] = $arr[$j];
			$arr[$j] = $temp;
		} else {
			//如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了。
			break;
		}
	}
	echo '已经排好序的前半段数组:';
	print_r(array_slice($arr,0,$i));
}




// 15  9  8  1  4 11  7 12 13  6  5  3 16  2 10 14
//
//  9 15  8  1  4 11  7 12 13  6  5  3 16  2 10 14
//
//  8  9 15  1  4 11  7 12 13  6  5  3 16  2 10 14
//
//  1  8  9 15  4 11  7 12 13  6  5  3 16  2 10 14
//
//  1  4  8  9 15 11  7 12 13  6  5  3 16  2 10 14
//
//  1  4  8  9 11 15  7 12 13  6  5  3 16  2 10 14
//
//  1  4  7  8  9 11 15 12 13  6  5  3 16  2 10 14
//
//  1  4  7  8  9 11 12 15 13  6  5  3 16  2 10 14
//
//  1  4  7  8  9 11 12 13 15  6  5  3 16  2 10 14
//
//  1  4  6  7  8  9 11 12 13 15  5  3 16  2 10 14
//
//  1  4  5  6  7  8  9 11 12 13 15  3 16  2 10 14
//
//  1  3  4  5  6  7  8  9 11 12 13 15 16  2 10 14
//
//  1  3  4  5  6  7  8  9 11 12 13 15 16  2 10 14
//
//  1  2  3  4  5  6  7  8  9 11 12 13 15 16 10 14
//
//  1  2  3  4  5  6  7  8  9 10 11 12 13 15 16 14
//
//  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16